//
// Created by jizhe hu on 2024/2/28.
//

#ifndef LEETCODE_GRAPH_H
#define LEETCODE_GRAPH_H

#include <vector>
#include <queue>
#include <functional>

using namespace std;

//! 797. 所有可能的路径
vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) {
    vector<vector<int>> res;
    function<void(vector<int>)> dfs = [&res, &dfs, &graph](vector<int> path){
        if(path.back() == (graph.size() - 1)) {
            res.push_back(path);
            return ;
        }
        int cur_node = path.back();
        if(count(path.begin(), path.end(), cur_node) == 2) return; // 存在环
        for(auto next_node : graph[cur_node]) {
            path.push_back(next_node);
            dfs(path);
            path.pop_back();
        }
    };

    dfs(vector<int>(1, 0));

    return res;
}

//! 200. 岛屿数量 bfs
int numIslands(vector<vector<char>>& grid){
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));

    function<void(int, int)> bfs = [&grid, &dir, &visited](int x, int y){
        queue<pair<int,int>> que;
        que.push(make_pair(x, y));
        visited[x][y] = true;
        while(!que.empty()) {
            pair<int ,int> cur = que.front();
            que.pop();
            int curx = cur.first, cury = cur.second; // 当前节点坐标
            for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
                if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
                if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 如果节点没被访问过
                    que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                    visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
                }
            }
        }
    };
    int res = 0;
    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(grid[i][j] == '1' && !visited[i][j]) {
                bfs(i, j);
                res++;
            }
        }
    }
    return res;
}

//! 200. 岛屿数量 dfs
int numIslands_(vector<vector<char>>& grid) {
    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
    int res = 0;

    function<void(int, int)> dfs = [&dfs, &grid, &visited](int x, int y) {
        int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if (!visited[nextx][nexty] && grid[nextx][nexty] == '1') { // 没有访问过的 同时 是陆地的

                visited[nextx][nexty] = true;
                dfs(nextx, nexty);
            }
        }

    };

    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(!visited[i][j] && grid[i][j] == '1') {
                visited[i][j] = true;
                dfs(i, j);
                res++;
            }
        }
    }

    return res;
}

//! 695. 岛屿的最大面积
int maxAreaOfIsland(vector<vector<int>>& grid) {
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // 表示四个方向
    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));

    function<int(int, int)> bfs = [&grid, &dir, &visited](int x, int y){
        int result = 0;
        queue<pair<int,int>> que;
        que.push(make_pair(x, y));
        visited[x][y] = true;
        while(!que.empty()) {
            pair<int ,int> cur = que.front();
            que.pop();
            result++;
            int curx = cur.first, cury = cur.second; // 当前节点坐标
            for (int i = 0; i < 4; i++) { // 开始向当前节点的四个方向左右上下去遍历
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1]; // 获取周边四个方向的坐标
                if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 坐标越界了，直接跳过
                if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // 如果节点没被访问过
                    que.push({nextx, nexty});  // 队列添加该节点为下一轮要遍历的节点
                    visited[nextx][nexty] = true; // 只要加入队列立刻标记，避免重复访问
                }
            }
        }
        return result;
    };
    int res = 0;
    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(grid[i][j] == 1 && !visited[i][j]) {
                res = max(res, bfs(i, j));
            }
        }
    }
    return res;
}

//! 1020. 飞地的数量
int numEnclaves(vector<vector<int>>& grid) {
    int res = 0;

    function<void(int, int)> dfs = [&dfs, &grid, &res](int x, int y) {
        int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
        grid[x][y] = 0;
        res++;

        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size() || grid[nextx][nexty] == 0) continue;  // 越界了，直接跳过
            dfs(nextx, nexty);
        }
    };

    for(int i=0; i<grid.size(); i++) {
        if(grid[i][0] == 1) dfs(i, 0);
        if(grid[i][grid[0].size() - 1] == 1) dfs(i, grid[0].size() - 1);
    }

    for(int i=0; i<grid[0].size(); i++) {
        if(grid[0][i] == 1) dfs(0, i);
        if(grid[grid.size() - 1][i] == 1) dfs(grid.size() - 1, i);
    }

    res = 0;

    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(grid[i][j] == 1) {
                dfs(i, j);
            }
        }
    }
    return res;
}

//! 130.被围绕的区域
void solve(vector<vector<char>>& grid) {
    vector<vector<bool>> need_changed(grid.size(), vector<bool>(grid[0].size(), true));
    function<void(int, int)> dfs = [&dfs, &grid, &need_changed](int x, int y) {
        int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
        need_changed[x][y] = false;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size() || grid[nextx][nexty] == 'X' || !need_changed[nextx][nexty]) continue;  // 越界了，直接跳过
            dfs(nextx, nexty);
        }
    };

    for(int i=0; i<grid.size(); i++) {
        if(grid[i][0] == 'O') dfs(i, 0);
        if(grid[i][grid[0].size() - 1] == 'O') dfs(i, grid[0].size() - 1);
    }

    for(int i=0; i<grid[0].size(); i++) {
        if(grid[0][i] == 'O') dfs(0, i);
        if(grid[grid.size() - 1][i] == 'O') dfs(grid.size() - 1, i);
    }

    for(int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(grid[i][j] == 'O' && need_changed[i][j]) {
                grid[i][j] = 'X';
            }
        }
    }
    return;
}

//! 417. 太平洋大西洋水流问题
vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    vector<vector<int>> res;
    vector<vector<bool>> visited_p(heights.size(), vector<bool>(heights[0].size(), false));
    vector<vector<bool>> visited_a(heights.size(), vector<bool>(heights[0].size(), false));

    function<void(int, int, vector<vector<bool>>&)> dfs = [&heights, &dfs](int x, int y, vector<vector<bool>> &visited){
        int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= heights.size() || nexty < 0 || nexty >= heights[0].size()) continue;  // 越界了，直接跳过
            if(!visited[nextx][nexty] && heights[x][y] <= heights[nextx][nexty]) dfs(nextx, nexty, visited);
        }
    };

    for(int i=0; i<heights[0].size(); i++) {
        if(!visited_p[0][i]) dfs(0, i, visited_p);
        if(!visited_a[heights.size() - 1][i]) dfs(heights.size() - 1, i, visited_a);
    }

    for(int i=0; i<heights.size(); i++) {
        if(!visited_p[i][0]) dfs(i, 0, visited_p);
        if(!visited_a[i][heights[0].size() - 1]) dfs(i, heights[0].size() - 1, visited_a);
    }

    for(int i=0; i<heights.size(); i++) {
        for(int j=0; j<heights[0].size(); j++) {
            if(visited_a[i][j] && visited_p[i][j]) res.push_back({i, j});
        }
    }

    return res;
}

//! 841. 钥匙和房间
bool canVisitAllRooms(vector<vector<int>>& rooms) {
    vector<bool> allKeys(rooms.size(), false);
    allKeys[0] = true;
    vector<bool> visited(rooms.size(), false);
    function<void(int )> dfs = [&allKeys, &dfs, &visited, &rooms](int i){
        if(visited[i]) return;
        visited[i] = true;
        for(auto key : rooms[i]) {
            allKeys[key] = true;
        }
        for(int x=0; x<allKeys.size(); x++) {
            if(allKeys[x] && !visited[x]) dfs(x);
        }
        return;
    };

    dfs(0);
    for(bool key : allKeys) {
        if(!key) return false;
    }
    return true;
}

int islandPerimeter(vector<vector<int>>& grid) {
    int res = 0;
    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
    function<void(int, int)> dfs = [&grid, &dfs, &visited, &res](int x, int y){
        int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
        visited[x][y] = true;
        res += 4;

        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // 越界了，直接跳过
            if(grid[nextx][nexty] == 1) {
                res--;
                if(!visited[nextx][nexty]) dfs(nextx, nexty);
            }
        }
    };
    for (int i=0; i<grid.size(); i++) {
        for(int j=0; j<grid[0].size(); j++) {
            if(grid[i][j] == 1 && !visited[i][j]) {
                dfs(i, j);
            }
        }
    }

    return res;
}

//! 1971. 寻找图中是否存在路径
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    vector<int> father(n);
    for(int i=0; i<n; i++) {
        father[i] = i;
    }
    function<int(int)> find = [&father, &find](int u){
        return u == father[u] ? u : father[u] = find(father[u]);
    };
    function<bool(int, int)> isSame = [&find, &father](int u, int v) {
        return find(u) == find(v);
    };
    function<void(int, int)> join = [&find, &father](int u, int v) {
        u = find(u); // 寻找u的根
        v = find(v); // 寻找v的根
        if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        father[v] = u;
    };
    for(int i=0; i<edges.size(); i++) {
        join(edges[i][0], edges[i][1]);
    }
    return isSame(source, destination);
}

//! 684. 冗余连接
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    vector<int> father(n + 1);
    for(int i=0; i<n; i++) {
        father[i] = i;
    }
    function<int(int)> find = [&father, &find](int u){
        return u == father[u] ? u : father[u] = find(father[u]);
    };
    function<bool(int, int)> isSame = [&find, &father](int u, int v) {
        return find(u) == find(v);
    };
    function<void(int, int)> join = [&find, &father](int u, int v) {
        u = find(u); // 寻找u的根
        v = find(v); // 寻找v的根
        if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        father[v] = u;
    };
    vector<int> res;
    for(int i=0; i<n; i++) {
        if(isSame(edges[i][0], edges[i][1])) {
            res = edges[i];
            continue;
        }
        join(edges[i][0], edges[i][1]);
    }
    return res;
}

//! 685. 冗余连接 II
vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
    int n = edges.size();
    vector<int> father(n + 1);
    for(int i=0; i<n; i++) {
        father[i] = i;
    }
    function<int(int)> find = [&father, &find](int u){
        return u == father[u] ? u : father[u] = find(father[u]);
    };
    function<bool(int, int)> isSame = [&find, &father](int u, int v) {
        return find(u) == find(v);
    };
    function<void(int, int)> join = [&find, &father](int u, int v) {
        u = find(u); // 寻找u的根
        v = find(v); // 寻找v的根
        if (u == v) return ; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回
        father[v] = u;
    };
    vector<int> res;
    for(int i=0; i<n; i++) {
        if(isSame(edges[i][0], edges[i][1])) {
            res = edges[i];
            continue;
        }
        join(edges[i][0], edges[i][1]);
    }
    return res;
}
#endif //LEETCODE_GRAPH_H
